home *** CD-ROM | disk | FTP | other *** search
/ Amiga Tools 3 / Amiga Tools 3.iso / grafik / raytracing / rayshade-4.0.6.3 / libray / libobj / csg.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-09  |  11.0 KB  |  477 lines
  1. /*
  2.  * csg.c
  3.  *
  4.  * Copyright (C) 1991, Rod G. Bogart, Craig E. Kolb
  5.  * All rights reserved.
  6.  *
  7.  * This software may be freely copied, modified, and redistributed
  8.  * provided that this copyright notice is preserved on all copies.
  9.  *
  10.  * You may not distribute this software, in whole or in part, as part of
  11.  * any commercial product without the express consent of the authors.
  12.  *
  13.  * There is no warranty or other guarantee of fitness of this software
  14.  * for any purpose.  It is provided solely "as is".
  15.  *
  16.  * csg.c,v 4.1 1994/08/09 07:58:20 explorer Exp
  17.  *
  18.  * csg.c,v
  19.  * Revision 4.1  1994/08/09  07:58:20  explorer
  20.  * Bump version to 4.1
  21.  *
  22.  * Revision 1.1.1.1  1994/08/08  04:52:08  explorer
  23.  * Initial import.  This is a prerelease of 4.0.6enh3, or 4.1 possibly.
  24.  *
  25.  * Revision 4.0  91/07/17  14:37:00  kolb
  26.  * Initial version.
  27.  * 
  28.  */
  29. #include "geom.h"
  30. #include "csg.h"
  31.  
  32. #define csg_set_enter(l, f) ((l)->data[0].enter = (f) + 1)
  33.  
  34. static Methods *iCsgMethods = NULL;
  35. static char csgName[] = "csg";
  36.  
  37. static int    CsgUnionInt(), CsgDifferenceInt(),
  38.         CsgIntersectInt();
  39. static void    CsgHitlistCopy(), CsgSetBounds();
  40.  
  41. Csg *
  42. CsgCreate(op)
  43. int op;
  44. {
  45.     Csg *csg;
  46.  
  47.     csg = (Csg *)share_malloc(sizeof(Csg));
  48.     csg->operator = op;
  49.     csg->obj1 = csg->obj2 = (Geom *)NULL;
  50.  
  51.  
  52.     switch(op) {
  53.         case CSG_UNION:
  54.             csg->intmeth = CsgUnionInt;
  55.             break;
  56.         case CSG_INTERSECT:
  57.             csg->intmeth = CsgIntersectInt;
  58.             break;
  59.         case CSG_DIFFERENCE:
  60.             csg->intmeth = CsgDifferenceInt;
  61.             break;
  62.         default:
  63.             RLerror(RL_ABORT, "Unknown csg op type %d?\n",op);
  64.     }
  65.     return csg;
  66. }
  67.  
  68. Methods *
  69. CsgMethods()
  70. {
  71.     if (iCsgMethods== (Methods *)NULL) {
  72.         iCsgMethods = MethodsCreate();
  73.         iCsgMethods->create = (GeomCreateFunc *)CsgCreate;
  74.         iCsgMethods->convert = CsgConvert;
  75.         iCsgMethods->methods = CsgMethods;
  76.         iCsgMethods->name = CsgName;
  77.         iCsgMethods->intersect = CsgIntersect;
  78.         iCsgMethods->bounds = CsgBounds;
  79.         iCsgMethods->checkbounds = TRUE;
  80.         iCsgMethods->closed = TRUE;
  81.     }
  82.     return iCsgMethods;
  83. }
  84.  
  85. char *
  86. CsgName()
  87. {
  88.     return csgName;
  89. }
  90.  
  91. csg_intersect_objs(csg, ray, hit1, hit2, mindist, dist1, dist2)
  92. Csg *csg;
  93. Ray *ray;
  94. HitList *hit1, *hit2;
  95. Float mindist, *dist1, *dist2;
  96. {
  97.     int operator;
  98.  
  99.     hit1->nodes = 0;
  100.     hit2->nodes = 0;
  101.     *dist1 = FAR_AWAY;
  102.     *dist2 = FAR_AWAY;
  103.     operator = csg->operator;
  104.  
  105.     if (!intersect(csg->obj1, ray, hit1, mindist, dist1) &&
  106.         ((operator == CSG_INTERSECT) || (operator == CSG_DIFFERENCE))) {
  107.         /*
  108.          * Intersection and Difference cases: if you miss the first
  109.          * object, you missed the whole thing.
  110.          */
  111.         return FALSE;
  112.     }
  113.  
  114.     if (!intersect(csg->obj2, ray, hit2, mindist, dist2) &&
  115.         ((operator == CSG_INTERSECT) ||
  116.          (hit1->nodes == 0) && (operator == CSG_UNION))) {
  117.         /*
  118.          * Intersect case:  if you miss either object, you miss whole
  119.          * Union case: if you miss both object, you miss whole
  120.          */
  121.         return FALSE;
  122.     }
  123.  
  124.     return TRUE;
  125. }
  126.  
  127. int
  128. csg_enter_obj(hitp)
  129. HitList *hitp;
  130. {
  131.     if (hitp->data[0].enter)
  132.         return hitp->data[0].enter - 1;
  133.  
  134.     return PrimEnter(hitp->data[0].obj, &hitp->data[0].ray,
  135.             hitp->data[0].mindist, hitp->data[0].dist);
  136. }
  137.  
  138. static int
  139. CsgUnionInt(ray, hit1p, hit2p, dist1, dist2, hitclose, distclose)
  140. Ray *ray;
  141. HitList *hit1p, *hit2p, **hitclose;
  142. Float dist1, dist2, *distclose;
  143. {
  144.     Float distnext;
  145.     HitList hitnext, *hittmp;
  146.  
  147.     while (TRUE) {
  148.         if (hit2p->nodes == 0 ||
  149.             csg_enter_obj(hit2p)) {
  150.             /* return hit1 */
  151.             *hitclose = hit1p;
  152.             *distclose = dist1;
  153.             csg_set_enter(hit1p, csg_enter_obj(hit1p));
  154.             return TRUE;
  155.         } else {
  156.             distnext = FAR_AWAY;
  157.             hitnext.nodes = 0;
  158.             if (!intersect(hit1p->data[hit1p->nodes-1].obj,
  159.                 ray, &hitnext, dist2+EPSILON, &distnext)) {
  160.                 /*
  161.                  * None of obj1 beyond, return hit2 (leaving)
  162.                  */
  163.                 *hitclose = hit2p;
  164.                 *distclose = dist2;
  165.                 csg_set_enter(hit2p, FALSE);
  166.                 return TRUE;
  167.             } else {
  168.                 /*
  169.                  * Since hit1 is supposed to be the close one,
  170.                  * swap them and copy hitnext into hit2.
  171.                       */
  172.                 hittmp = hit1p;
  173.                 hit1p = hit2p;
  174.                 hit2p = hittmp;
  175.                 dist1 = dist2;
  176.                 CsgHitlistCopy(&hitnext, hit2p);
  177.                 dist2 = distnext;
  178.                 /* and continue */
  179.             }
  180.         }
  181.     }
  182. }
  183.  
  184. static int
  185. CsgIntersectInt(ray, hit1p, hit2p, dist1, dist2, hitclose, distclose)
  186. Ray *ray;
  187. HitList *hit1p, *hit2p, **hitclose;
  188. Float dist1, dist2, *distclose;
  189. {
  190.     HitList *hittmp, hitnext;
  191.     Float distnext;
  192.  
  193.     while (TRUE) {
  194.         if (!csg_enter_obj(hit2p)) {
  195.             /* Ray is leaving obj2 */
  196.             /* Return hit1 info */
  197.             *hitclose = hit1p;
  198.             *distclose = dist1;
  199.             csg_set_enter(hit1p, csg_enter_obj(hit1p));
  200.             return TRUE;
  201.         } else {
  202.             distnext = FAR_AWAY;
  203.             hitnext.nodes = 0;
  204.             if (!intersect(hit1p->data[hit1p->nodes-1].obj,
  205.                 ray, &hitnext, dist2+EPSILON, &distnext)) {
  206.                 /*
  207.                  * None of obj1 beyond, so return miss
  208.                  */
  209.                 return FALSE;
  210.             } else {
  211.                 /*
  212.                  * Since hit1 is supposed to be the
  213.                  * close one, swap them and copy
  214.                  * hitnext into hit2.
  215.                  */
  216.                 hittmp = hit1p;
  217.                 hit1p = hit2p;
  218.                 hit2p = hittmp;
  219.                 dist1 = dist2;
  220.                 CsgHitlistCopy(&hitnext, hit2p);
  221.                 dist2 = distnext;
  222.                 /* and continue */
  223.             }
  224.         }
  225.     }
  226. }
  227.  
  228. static int
  229. CsgDifferenceInt(ray, hit1p, hit2p, dist1, dist2, hitclose, distclose)
  230. Ray *ray;
  231. HitList *hit1p, *hit2p, **hitclose;
  232. Float dist1, dist2, *distclose;
  233. {
  234.     Float distnext;
  235.     HitList hitnext;
  236.  
  237.     while (TRUE) {
  238.         if (dist1 < dist2) {
  239.             if (hit2p->nodes == 0 ||
  240.                 csg_enter_obj(hit2p)) {
  241.                 /* return hit1 */
  242.                 *hitclose = hit1p;
  243.                 *distclose = dist1;
  244.                 csg_set_enter(hit1p, csg_enter_obj(hit1p));
  245.                 return TRUE;
  246.             } else {
  247.                 distnext = FAR_AWAY;
  248.                 hitnext.nodes = 0;
  249.                 if (!intersect(hit1p->data[hit1p->nodes-1].obj,
  250.                     ray, &hitnext, dist2+EPSILON, &distnext)) {
  251.                     /*
  252.                      * None of obj1 beyond, so
  253.                      * return miss
  254.                      */
  255.                     return FALSE;
  256.                 } else {
  257.                     dist1 = distnext;
  258.                     CsgHitlistCopy(&hitnext, hit1p);
  259.                     /* and continue */
  260.                 }
  261.             }
  262.         } else { /* dist1 <= dist2 */
  263.             if (hit1p->nodes == 0) {
  264.                 /* return a miss */
  265.                 return FALSE;
  266.             }
  267.             if (!csg_enter_obj(hit1p)) {
  268.                 /*
  269.                  * return hit2, but invert hit2
  270.                  * Enter/Leave flag
  271.                  */
  272.                 *hitclose = hit2p;
  273.                 *distclose = dist2;
  274.                 csg_set_enter(hit2p, !csg_enter_obj(hit2p));
  275.                 return TRUE;
  276.             } else {
  277.                 distnext = FAR_AWAY;
  278.                 hitnext.nodes = 0;
  279.                 if (!intersect(hit2p->data[hit2p->nodes-1].obj,
  280.                     ray, &hitnext, dist1+EPSILON, &distnext)) {
  281.                     /*
  282.                      * None of obj2 beyond, so
  283.                      * return hit1
  284.                      */
  285.                     *hitclose = hit1p;
  286.                     *distclose = dist1;
  287.                     /* we know we're entering obj1 */
  288.                     csg_set_enter(hit1p, TRUE);
  289.                     return TRUE;
  290.                 } else {
  291.                     dist2 = distnext;
  292.                     CsgHitlistCopy(&hitnext, hit2p);
  293.                     /* and continue */
  294.                 }
  295.             }
  296.         }
  297.     }
  298. }
  299.  
  300. int
  301. CsgIntersect(csg, ray, hitlist, mindist, maxdist)
  302. Csg *csg;
  303. Ray *ray;
  304. HitList *hitlist;
  305. Float mindist, *maxdist;
  306. {
  307.     Float dist1, dist2, disttmp, distclose;
  308.     HitList hit1, hit2, *hit1p, *hit2p, *hitclose;
  309.  
  310.     hit1p = &hit1;
  311.     hit2p = &hit2;
  312.     if (!csg_intersect_objs(csg, ray, hit1p, hit2p, mindist,
  313.         &dist1, &dist2)) {
  314.         /* missed the csg object */
  315.         return FALSE;
  316.     }
  317.  
  318.     if ((dist1 > dist2) &&
  319.         (csg->operator == CSG_UNION || csg->operator == CSG_INTERSECT)) {
  320.         /* swap so 1 is closest (except in difference case) */
  321.         disttmp = dist2;  
  322.         dist2 = dist1;  
  323.         dist1 = disttmp;
  324.         hit1p = &hit2;  
  325.         hit2p = &hit1;
  326.     }
  327.  
  328.     /*
  329.      * Call appropriate intersection method.  If FALSE is return,
  330.      * no hit of any kind was found.
  331.      */
  332.     if (!(*csg->intmeth)(ray, hit1p, hit2p, dist1, dist2,
  333.         &hitclose, &distclose))
  334.         return FALSE;
  335.  
  336.     /*
  337.      * At this time, the closest hit is in hitclose and
  338.      * distclose.
  339.      */
  340.     if (distclose < mindist || distclose > *maxdist)
  341.         return FALSE;
  342.  
  343.     CsgHitlistCopy(hitclose, hitlist);
  344.     *maxdist = distclose;
  345.     return TRUE;
  346. }
  347.  
  348. static void
  349. CsgHitlistCopy(from, to)
  350. HitList *from, *to;
  351. {
  352.     int i;
  353.  
  354.     to->nodes = from->nodes;
  355.     for (i = 0; i < from->nodes; i++)
  356.         to->data[i] = from->data[i];
  357. }
  358.  
  359. static void
  360. CsgSetBounds(csg, bounds)
  361. Csg *csg;
  362. Float bounds[2][3];
  363. {
  364.     GeomComputeBounds(csg->obj1);
  365.     GeomComputeBounds(csg->obj2);
  366.  
  367.     switch (csg->operator) {
  368.     case CSG_UNION:
  369.         bounds[LOW][X] = min(csg->obj1->bounds[LOW][X], csg->obj2->bounds[LOW][X]);
  370.         bounds[HIGH][X] = max(csg->obj1->bounds[HIGH][X], csg->obj2->bounds[HIGH][X]);
  371.         bounds[LOW][Y] = min(csg->obj1->bounds[LOW][Y], csg->obj2->bounds[LOW][Y]);
  372.         bounds[HIGH][Y] = max(csg->obj1->bounds[HIGH][Y], csg->obj2->bounds[HIGH][Y]);
  373.         bounds[LOW][Z] = min(csg->obj1->bounds[LOW][Z], csg->obj2->bounds[LOW][Z]);
  374.         bounds[HIGH][Z] = max(csg->obj1->bounds[HIGH][Z], csg->obj2->bounds[HIGH][Z]);
  375.         break;
  376.     case CSG_INTERSECT:
  377.         bounds[LOW][X] = max(csg->obj1->bounds[LOW][X], csg->obj2->bounds[LOW][X]);
  378.         bounds[HIGH][X] = min(csg->obj1->bounds[HIGH][X], csg->obj2->bounds[HIGH][X]);
  379.         bounds[LOW][Y] = max(csg->obj1->bounds[LOW][Y], csg->obj2->bounds[LOW][Y]);
  380.         bounds[HIGH][Y] = min(csg->obj1->bounds[HIGH][Y], csg->obj2->bounds[HIGH][Y]);
  381.         bounds[LOW][Z] = max(csg->obj1->bounds[LOW][Z], csg->obj2->bounds[LOW][Z]);
  382.         bounds[HIGH][Z] = min(csg->obj1->bounds[HIGH][Z], csg->obj2->bounds[HIGH][Z]);
  383.         break;
  384.     case CSG_DIFFERENCE:
  385.         bounds[LOW][X] = csg->obj1->bounds[LOW][X];
  386.         bounds[HIGH][X] = csg->obj1->bounds[HIGH][X];
  387.         bounds[LOW][Y] = csg->obj1->bounds[LOW][Y];
  388.         bounds[HIGH][Y] = csg->obj1->bounds[HIGH][Y];
  389.         bounds[LOW][Z] = csg->obj1->bounds[LOW][Z];
  390.         bounds[HIGH][Z] = csg->obj1->bounds[HIGH][Z];
  391.         break;
  392.     default:
  393.         RLerror(RL_ABORT, "Unknown csg operator type %d?\n",
  394.             csg->operator);
  395.     }
  396. }
  397.  
  398. /*
  399.  * Return index of hitlist node closest to the leaf and not below any
  400.  * CSG object.
  401.  */
  402. int
  403. FirstCSGGeom(hitlist)
  404. HitList *hitlist;
  405. {
  406.     int i;
  407.  
  408.     /*
  409.      * UUUUGLY -- detect if obj is a CsgGeom by comparing
  410.      * methods with iCsgMethods.
  411.      */
  412.     for (i = hitlist->nodes -1; i; i--)
  413.         if (hitlist->data[i].obj->methods == iCsgMethods)
  414.             return i;
  415.     return 0;
  416. }
  417.  
  418. void
  419. CsgBounds(csg, bounds)
  420. Csg *csg;
  421. Float bounds[2][3];
  422. {
  423.     CsgSetBounds(csg, csg->bounds);
  424.     BoundsCopy(csg->bounds, bounds);
  425. }
  426.  
  427. int
  428. CsgConvert(csg, list)
  429. Csg *csg;
  430. Geom *list;
  431. {
  432.         static int OpenAdvised = FALSE;
  433.         int prims = 0;
  434.  
  435.         if (!list || !list->next) {
  436.                 RLerror(RL_WARN, "CSG needs at least two objects.\n");
  437.                 return 0;
  438.         }
  439.         /*
  440.          * Things are put into lists backwards....
  441.          */
  442.         csg->obj2 = list;
  443.         if (!list->methods->closed && !OpenAdvised) {
  444.           RLerror(RL_ADVISE, "Performing CSG with non-closed object(s).\n");
  445.           OpenAdvised = TRUE;
  446.         }
  447.         prims += list->prims;
  448.         list = list->next;
  449.         while (list->next) {
  450.           csg->obj1 = GeomCsgCreate(csg->operator);
  451.           csg = (Csg*)csg->obj1->obj;
  452.           csg->obj2 = list;
  453.           if (!list->methods->closed && !OpenAdvised) {
  454.             RLerror(RL_ADVISE, "Performing CSG with non-closed object(s).\n");
  455.             OpenAdvised = TRUE;
  456.           }
  457.           prims += list->prims;
  458.           list = list->next;
  459.         }
  460.         csg->obj1 = list;
  461.         if (!list->methods->closed && !OpenAdvised) {
  462.           RLerror(RL_ADVISE, "Performing CSG with non-closed object(s).\n");
  463.           OpenAdvised = TRUE;
  464.         }
  465.         prims += list->prims;
  466.  
  467.         return prims;
  468. }
  469.  
  470. void
  471. CsgMethodRegister(meth)
  472. UserMethodType meth;
  473. {
  474.     if (iCsgMethods)
  475.         iCsgMethods->user = meth;
  476. }
  477.